package puzzle.projecteuler.p200;

import astudy.util.AdvMath;
import astudy.util.AdvMath.Factors;

public class Problem157B {

	/**
	 *    (p*a-10^n)(p*b-10^n) = 10^(2n)
	 * 
	 * => s*t = 10^(2n), 
	 *    p*a = 10^n + s
	 *    p*b = 10^n + t
	 *    
	 * => p | gcd(10^n+s, 10^n+t)
	 *    s = 2^u * 5^v
	 *    t = 2^(2n-u) * 5^(2n-v) 
	 *  
	 * @param args
	 */
	public static void main(String[] args) {

		int c = 0;
		for (int n = 1; n <= 9; n ++) {
			c += count(n);
		}
		System.out.println(c);
	}
	
	/**
	 * number of solutions
	 * @param n
	 * @return
	 */
	public static int count(int n) {
		int c = 0;
		for (int u = 0; u <= 2*n; u ++) {
			for (int v = 0; v <= 2*n; v ++) {
				c += count(n, u, v);
			}
		}
		return (c + count(n, n, n))/2;
	}
	
	public static int count(int n, int u, int v) {
		
		long a = (long)Math.pow(10, n);
		long s = (long)Math.pow(2, u)*(long)Math.pow(5, v);
		long t = (long)Math.pow(2, 2*n-u)*(long)Math.pow(5, 2*n-v);
		long m = AdvMath.gcd(a+s, a+t);
		
		int c = 1;
		Factors fs = AdvMath.factor(m);
		for (Long k: fs.keySet()) {
			c *= (fs.get(k)+1);
		}
		return c;
	}

}
